package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 1609. 奇偶树
 *
 * @Author liw
 * @Date 2021/5/30 15:29
 * @Version 1.0
 */
public class IsEvenOddTree {

    public static void main(String[] args) {
        IsEvenOddTree test = new IsEvenOddTree();
        boolean evenOddTree = test.isEvenOddTree(TreeNode.getInstance());
        System.out.println(evenOddTree);
    }

    public boolean isEvenOddTree(TreeNode root) {
        Queue<TreeNode> a = new LinkedList<>();
        Queue<TreeNode> b = new LinkedList<>();
        a.add(root);
        boolean flag = true;
        while (!a.isEmpty() || !b.isEmpty()) {
            if (flag) {
                int item = 0;
                while (!a.isEmpty()) {
                    TreeNode node = a.poll();
                    int val = node.val;
                    if ((val & 1) == 0 || val <= item) {
                        return false;
                    }
                    item = val;
                    if (node.left != null) {
                        b.offer(node.left);
                    }
                    if (node.right != null) {
                        b.offer(node.right);
                    }
                }
                flag = false;
            } else {
                int item = Integer.MAX_VALUE;
                while (!b.isEmpty()) {
                    TreeNode node = b.poll();
                    int val = node.val;
                    if ((val & 1) != 0 || val >= item) {
                        return false;
                    }
                    item = val;
                    if (node.left != null) {
                        a.offer(node.left);
                    }
                    if (node.right != null) {
                        a.offer(node.right);
                    }
                }
                flag = true;
            }
        }
        return true;
    }
}
